课件目录#

第一章：磁盘存储与页面布局 (Database Storage)
第二章：内存管理与缓冲池 (Buffer Pools)
第三章：日志结构存储与索引组织表 (Log-Structured & Index-Organized)
第四章：列式存储与压缩 (Column Stores & Compression)
第五章：哈希表数据结构 (Hash Tables)

第一章：磁盘存储与页面布局 (Database Storage)#

1. 核心概念解释#

面向磁盘的架构 (Disk-Oriented Architecture): 数据库假设主要数据存储在非易失性磁盘（HDD/SSD）上，虽然 CPU 只能直接操作内存中的数据，但系统必须负责在磁盘和内存之间来回移动数据（Pages）。
页 (Page): 数据库文件在磁盘上被划分为固定大小的块（通常为 4KB-16KB），称为“页”。它是读写操作的最小单位,。
槽式页面设计 (Slotted Pages): 這是行式存储中最常见的页面布局方式。页面头部包含一个槽数组（Slot Array），记录每条记录的偏移量。记录内容从页面底部向上增长，槽数组从顶部向下增长，以此解决变长记录的存储问题,。

2. 关键结论 / 公式 / 方法#

存储层级 (Hierarchy): 易失性存储（CPU 寄存器、L1-L3 缓存、DRAM）速度快但容量小且断电丢失；非易失性存储（SSD、HDD）速度慢但容量大且持久,。
访问延迟差异: 顺序访问（Sequential Access）通常远快于随机访问（Random Access），设计目标是尽量最大化顺序 I/O,。
Record ID (Record Identifier): 用于物理定位一条记录，通常由 File ID + Page ID + Slot Number 组成。
元数据 (Metadata): 数据库必须维护页目录（Page Directory）来追踪哪些页已被使用以及它们的位置。

3. 易混点或易错点提示#

OS Page vs. DB Page: 硬件页面通常是 4KB，操作系统页面也是 4KB，但数据库页面大小可以由数据库系统自定义（如 MySQL 默认 16KB）。数据库在写入大于原子写入单位（硬件页）的页面时，需额外机制保证崩溃安全,。
删除记录: 在槽式页面中删除记录时，通常不会立即移动数据，而是更新槽数组。由于槽数组提供了间接层（Indirection），移动页面内部的数据只需更新槽中的偏移量，而无需更改外部引用的 Record ID。

4. 简短复习小结#

数据库由磁盘上的文件组成，文件被切分为固定大小的页。槽式页面（Slotted Page）结构允许我们高效存储变长记录，并支持通过间接层重新组织页面内部数据。

第二章：内存管理与缓冲池 (Buffer Pools)#

1. 核心概念解释#

缓冲池 (Buffer Pool): 它是数据库在内存中分配的一块区域，用于缓存从磁盘读取的页。数组中的每个位置称为一个帧 (Frame)。
页表 (Page Table): 这是一个内存中的哈希表，用于映射 Page ID 到缓冲池中的 Frame 位置。它不同于磁盘上的“页目录”，它只记录当前在内存中的页,。
Pin (引用计数): 当一个线程读取某页时，会增加该页的 Pin 计数，防止该页被缓冲池置换出去（Evicted）。

2. 关键结论 / 公式 / 方法#

置换策略 (Replacement Policies):
- LRU (Least Recently Used): 维护时间戳链表，淘汰最久未使用的页。缺点是在全表扫描（Sequential Flooding）时会“污染”缓冲池,。
- Clock (时钟算法): LRU 的近似算法。使用引用位（Reference Bit），类似时钟指针扫描，若位为1则置0并跳过，若为0则淘汰。避免了维护 LRU 链表的开销,。
- LRU-K: 记录最后 K 次访问的历史，以此区分长期的频繁访问模式和单次扫描带来的突发访问。
Direct I/O: 数据库应绕过操作系统的文件系统缓存（OS Page Cache），使用 Direct I/O (O_DIRECT) 直接管理内存，避免双重拷贝和不可控的页面淘汰。

3. 易混点或易错点提示#

Locks vs. Latches:
- Locks: 逻辑层面的锁（如事务锁），保护数据库内容（如元组、表），由死锁检测机制管理。
- Latches: 物理层面的锁（类似 Mutex），保护内部数据结构（如页表、哈希表），要求持有时间极短，不进行死锁检测,。
不要使用 mmap: 尽管 mmap 看起来很方便（由 OS 管理内存），但 OS 无法理解数据库查询的上下文，导致错误的页面淘汰决策、I/O 阻塞和难以处理的错误（如 SIGBUS）,,。

4. 简短复习小结#

缓冲池是内存和磁盘之间的桥梁。为了性能和正确性，数据库系统必须自己管理内存（使用 CLOCK 或 LRU-K 算法），而不是依赖操作系统。核心目标是减少磁盘 I/O 并最大化页面在内存中的价值。

第三章：日志结构存储与索引组织表 (Log-Structured & Index-Organized)#

1. 核心概念解释#

索引组织存储 (Index-Organized Storage): 数据不仅仅存储在无序的堆文件（Heap File）中，而是直接存储在索引（通常是 B+树）的叶子节点中。主键查找非常快，但更新可能引起数据移动,。
日志结构存储 (Log-Structured / LSM Trees): 系统不允许直接覆盖更新数据，而是将新的插入和更新作为日志追加（Append-only）写入。包括内存中的 MemTable 和磁盘上的 SSTable,。

2. 关键结论 / 公式 / 方法#

LSM 架构:
- 写入: 先写入内存中的 MemTable（通常是跳表或树）。满后转为不可变的 SSTable 刷入磁盘,。
- 读取: 需检查 MemTable 和所有层级的 SSTable，读取可能较慢。使用 Bloom Filter 快速判断 key 是否不存在以优化读取,。
压缩 (Compaction): 后台进程将多个 SSTable 合并，移除被删除或覆盖的旧版本数据。
- Level Compaction: 每一层由互不重叠的 SSTable 组成，适合读取较多的场景。
- Universal Compaction: 类似于合并多个已排序的运行文件，适合写入极多的场景。

3. 易混点或易错点提示#

写放大 vs. 读放大: LSM 树通过顺序写入极大地优化了写入性能（避免了随机 I/O），但代价是读取性能下降（因为可能需要搜索多个文件）以及写放大（Compaction 过程中反复读写数据）。
删除操作: 在 LSM 中，删除并非物理删除，而是写入一个 Tombstone（墓碑）标记，表示该 Key 已被删除。

4. 简短复习小结#

LSM 树（如 RocksDB）通过追加写和后台压缩，牺牲了一定的读取性能来换取极高的写入吞吐量，非常适合写密集型负载。

第四章：列式存储与压缩 (Column Stores & Compression)#

1. 核心概念解释#

行式存储 (NSM): 连续存储一个元组的所有属性。适合 OLTP（事务处理），因为通常需要读取或更新整行数据。
列式存储 (DSM): 将同一列的数据连续存储。适合 OLAP（分析处理），因为查询通常只涉及少数几列，可以大量减少不必要的 I/O。
混合模型 (PAX): 在一个大的页（Row Group）内，内部按列组织数据。这是现代系统（如 Parquet, ORC）的主流做法。

2. 关键结论 / 公式 / 方法#

延迟物化 (Late Materialization): 尽可能晚地将列数据拼凑回行，允许直接在压缩数据上进行查询和过滤。
压缩算法: 列式存储由于数据类型单一，压缩率极高。
- Run-Length Encoding (RLE): 存储 (值, 长度) 对，适合大量重复数据（如性别列排序后）。
- Bitmap Encoding: 对低基数数据使用位图标记。
- Delta Encoding: 存储与基准值的差值（如时间戳）。
- Dictionary Compression: 将频繁出现的字符串替换为整数代码，不仅压缩数据，还能加速字符串比较（直接比较整数）,。

3. 易混点或易错点提示#

定长要求: 许多压缩和处理优化依赖于定长数据，以便通过偏移量直接跳转。变长数据通常需要转换为定长（如字典编码）,。
字典编码的顺序保留: 如果字典是按值排序的，支持在压缩数据上直接进行范围查询（Range Queries），而无需解压。

4. 简短复习小结#

对于分析型工作负载（OLAP），列式存储通过只读取需要的列和高效的压缩算法，性能远超行式存储。现代系统多采用 PAX 格式兼顾两者优点。

第五章：哈希表数据结构 (Hash Tables)#

1. 核心概念解释#

哈希表: 将键映射到值的无序关联数组。平均时间复杂度 O(1)。
哈希函数: 数据库不关心加密安全性，只关心速度和低冲突率（如 XXHash3）,。

2. 关键结论 / 公式 / 方法#

静态哈希 (Static Hashing): 假设表大小固定。
- 线性探测 (Linear Probing): 发生冲突时，线性向下扫描寻找空槽。实现简单，对 CPU 缓存友好，速度极快,。
- Cuckoo Hashing: 使用多个哈希函数和多个位置。发生冲突时，将旧数据“踢出”去寻找新位置。查找保证 O(1)。
动态哈希 (Dynamic Hashing): 表大小可变。
- 链式哈希 (Chained Hashing): 每个槽维护一个溢出桶链表。
- 可扩展哈希 (Extendible Hashing): 使用全局和局部深度（Global/Local Depth）位掩码，只分裂溢出的桶并重新指向目录指针，无需全表重哈希。
- 线性哈希 (Linear Hashing): 使用分裂指针（Split Pointer），按顺序逐步分裂桶，平滑扩展。

3. 易混点或易错点提示#

Tombstones (墓碑): 在线性探测中删除元素不能直接清空槽位，否则会截断后续冲突元素的查找路径。必须放置 Tombstone 标记该位置为“已删除但曾被占用”。
线性探测 vs. 线性哈希: 名字相似但完全不同。线性探测是解决冲突的策略（静态），线性哈希是表扩容的策略（动态）。